package com.txy.alth.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 部分背包-贪心算法
 */
public class Bag1 {
    double max = 0;
    public void getMaxValue(Goods[] glist) {
        Goods[] glist2 = sort(glist);
        double sum_w = 0.0; //当前总重量
        for(int i=0;i<glist2.length;i++) {
            sum_w += glist2[i].weight;
            if(sum_w<=max) {
                System.out.println(glist2[i].name + "取" + glist2[i].weight + "kg");
            }else {
                System.out.println(glist2[i].name + "取" + (max - (sum_w - glist2[i].weight)) + "kg");
                return;
            }
        }
    }

    private Goods[] sort(Goods[] goods) {
        Arrays.sort(goods, new Comparator<Goods>() {
            public int compare(Goods o1, Goods o2) {
                if(o1.value > o2.value) {
                    return -1;
                }else if(o1.value < o2.value) {
                    return 1;
                }else return 0;
            }
        });
        return goods;
    }

    public static void main(String[] args) {
        Bag1 bag1 = new Bag1();
        Goods g1 = new Goods("A", 10, 60);
        Goods g2 = new Goods("B", 20, 100);
        Goods g3 = new Goods("C", 30, 120);
        bag1.max = 50;
        bag1.getMaxValue(new Goods[]{g1,g2,g3});
    }
}
